package edu.gatech.coc.sirana.detection;

import java.util.ArrayList;

import net.util.Debug;

/** 
 * Levenshtein distance
 */
 
public class LevenshteinDistance {
	public double computeNormalizedEditDistance(SRCycleAttribute src1, SRCycleAttribute src2){
		int editDis = computeEventEditDistance(src1, src2);
		int comLength = src1.findEventString().length() + src2.findEventString().length();
		
		return (double)editDis/comLength;
	}
	
	public int computeEventEditDistance(SRCycleAttribute src1, SRCycleAttribute src2){
		String s1 = src1.findEventString();
		String s2 = src2.findEventString();
		
		int editDis = compute(s1, s2);
		
		return editDis;
	}
	
	public int computeStringList(ArrayList<String> s1, ArrayList<String> s2){
 		int[][] dp = new int[s1.size() + 1][s2.size() + 1];
 		for (int i = 0; i < dp.length; i++) {
 			for (int j = 0; j < dp[i].length; j++) {
 
 				dp[i][j] = i == 0 ? j : j == 0 ? i : 0;
 
 				if (i > 0 && j > 0) {
 
 					if (s1.get(i - 1) == s2.get(j - 1))
 						dp[i][j] = dp[i - 1][j - 1];
 
 					else
 						dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(
 								dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1));
 
 				}
 			}
 		}
 		
 		int d = dp[s1.size()][s2.size()]; 
		Debug.println("compute :" + d + "\n\t"  + s1.toString() + "\n\t" + s2.toString());
 		return d;		
	}
	
 	public int compute(String s1, String s2) {
 		int[][] dp = new int[s1.length() + 1][s2.length() + 1];
 
 		for (int i = 0; i < dp.length; i++) {
 			for (int j = 0; j < dp[i].length; j++) {
 
 				dp[i][j] = i == 0 ? j : j == 0 ? i : 0;
 
 				if (i > 0 && j > 0) {
 
 					if (s1.charAt(i - 1) == s2.charAt(j - 1))
 						dp[i][j] = dp[i - 1][j - 1];
 
 					else
 						dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(
 								dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1));
 
 				}
 			}
 		}
 		return dp[s1.length()][s2.length()];
 
 	}
 	 	
 	public  int compute(int[] n1, int[] n2){
 		int[][] dp = new int[n1.length + 1][n2.length + 1];
 		
 		for (int i = 0; i < dp.length; i++) {
 			for (int j = 0; j < dp[i].length; j++) {
 
 				dp[i][j] = i == 0 ? j : j == 0 ? i : 0;
 
 				if (i > 0 && j > 0) {
 
 					if (n1[i - 1] == n2[j - 1])
 						dp[i][j] = dp[i - 1][j - 1];
 
 					else
 						dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(
 								dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1));
 
 				}
 			}
 		}
 		return dp[n1.length][n2.length];
 	}
 	
 	public static void main(String[] args) {
 		LevenshteinDistance distance = new LevenshteinDistance();
 		int[] n1 = {1, 1, 2, 3, 5, 7};
 		int[] n2 = {1, 5, 4, 7};
 		Debug.printIntArray(n1);
 		Debug.printIntArray(n2);
 		Debug.println("l-dis=" + distance.compute(n1, n2));
 		
 		Debug.exit();
 		System.out.println("12345: 145=" + distance.compute("12345", "145"));
 		System.out.println("vintners: writers=" + distance.compute("vintners", "writers"));
 		System.out.println("vintners:=" + distance.compute("vintners", ""));
 		System.out.println(":=" + distance.compute("", ""));
 
 	}
 }